package com.faiz.algorithm;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

//数据流的中位数
public class MedianInDataStream {
    private static Queue<Integer> minHeap = new PriorityQueue<>();
    private static Queue<Integer> maxHeap = new PriorityQueue<>((x, y) -> (y - x));

    public static void addNum(int num) {
        if (minHeap.size() != maxHeap.size()) {
            minHeap.add(num);
            maxHeap.add(minHeap.poll());
        } else {
            maxHeap.add(num);
            minHeap.add(maxHeap.poll());
        }
    }

    public static double findMedian() {
        return minHeap.size() != maxHeap.size() ? minHeap.peek() : (minHeap.peek() + maxHeap.peek()) / 2.0;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6};
        Arrays.stream(nums).forEach(MedianInDataStream::addNum);
        System.out.println(findMedian());
    }

}

